#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int n = nums.size();
        int mod = 1e9 + 7;
        long long dp[1 << n][n];
        long long ans = 0;
        memset(dp, 0, sizeof dp);
        for (int i = 1; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if ((i >> j) & 1) {
                    int U = i ^ (1 << j);
                    //cout<<U<<endl;
                    if (U == 0) {
                        dp[i][j] = 1;
                        continue;
                    }
                    for (int jj = 0; jj < n; jj++) {
                        if (nums[jj] % nums[j] == 0 || nums[j] % nums[jj] == 0) {
                            dp[i][j] = (dp[i][j] + dp[U][jj]) % mod;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            ans = (ans + dp[(1 << n) - 1][i]) % mod;
        }
        return ans;
    }
};